// scaup - Scala up!
// (c) 2008-2010, Normen Müller, normen.mueller@gmail.com  
// $Id: E.scala 58 2010-04-05 16:39:46Z normen.mueller $
package scaup.eq

/** 
 * @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 * @version 0.0.3 */
case class Slit[T](val before: Option[Seq[T]],val focus: Option[T],val after: Seq[T])
  
/** An equivalence system.
 * 
 *  An equivalence system is a set of equivalence relations.
 * 
 *  Q: Why contravariant type constructor?
 *  A: If S <: T then E[T] <: E[S] wrt. the cardinality of equal elements.  For example, XML <: AnyRef but
 *     within the equivalence model model of XML more elements are considers to be equal than within
 *     the equivalence model model of AnyRef
 *
 * @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 * @version 0.0.3 */
trait EquivalenceSystem[-T] {  
  def findEquivTo[S <: T](elem: S, ctx: Seq[S]): Slit[S] = findEquivTo(elem, ctx, Nil)
  
  private def findEquivTo[S <: T](elem: S, ctx: Seq[S], acc: Seq[S]): Slit[S] = ctx match {
    case Nil | Seq.empty =>
      Slit(None,None,acc)
      
    case _ if equiv(elem,ctx(0)) =>
      if(ordered(elem)) acc match {
        case Nil | Seq.empty => Slit(None, Some(ctx(0)), ctx.drop(1))
        case _               => Slit(Some(acc), Some(ctx(0)), ctx.drop(1))
      } else Slit(None, Some(ctx(0)),acc ++ ctx.drop(1))
      
    case _ =>
      findEquivTo(elem, ctx.drop(1), acc ++ Seq(ctx(0)))
  }
  
  def equiv[S <: T](l: S, r: S): Boolean = l == r
  
  def equiv[S <: T](ls: Seq[S], rs: Seq[S]): Boolean = ls.length == rs.length && (ls forall (e => rs exists (equiv(e,_))))
  
  def ordered[S <: T](l: S): Boolean = true
}

///////////////////////////////////////////////////////////////////////////
case class Spec(alts: List[Constraints])

case class Constraints(
  reqAnnos: Set[String],
  optAnnos: Set[String], 
  reqOrdConsts: List[String],
  optOrdConsts: List[String],
  reqUOrdConsts: Set[String],
  optUOrdConsts: Set[String])

trait EquivalenceSystem2[M <: {def get(key: String): Option[Seq[T]]}, -T] {  
  def equivspec(l: T): Option[Spec] = None
  
  def findEquivTo[S <: T](elem: S, ctx: Seq[S]): Slit[S] = findEquivTo(elem, ctx, Nil)
  
  def ordered[S <: T](l: S): Boolean = true
  
  def nameOf[S <: T](l: S): String
  
  def annotationsOf[S <: T](l: S): M
  
  def constituentsOf[S <: T](l: S): Seq[S]
  
  private def equiv[S <: T](l: S, r: S): Boolean =
    if(nameOf(l) == nameOf(r)) equivspec(l) match {
      case Some(Spec(Nil)) => true                        // equal by name
      case Some(spec)      => compareTo(spec.alts, l, r)  // equal by spec
      case None            => l == r                      // equal by XML deep equality
    } else false 
  
  private def equivSeq[S <: T](l: List[S], r: List[S]): Boolean =
    if(l.size == r.size) (l, r) match {
      case (lhd :: ltl, rhd :: rtl) => equiv(lhd, rhd) && equivSeq(ltl, rtl)
      case (Nil, Nil)               => true
      case _                        => false
    } else false
  
  private def equivSet[S <: T](l: List[S], r: List[S]): Boolean = 
    (  (l.size == r.size)
    && (l.elements forall (le => r.elements exists (re => equiv(le, re))))
    )
    
  private def compareTo[S <: T](alts: List[Constraints], l: S, r: S): Boolean = alts match {
    case hd :: tl =>
      (  (compareAnnos(hd.reqAnnos, hd.optAnnos, l, r))
      && (compareConsts(hd.reqOrdConsts, hd.reqUOrdConsts, hd.optOrdConsts, hd.optUOrdConsts, l, r))
      ) || compareTo(tl, l, r)
    case Nil      => false
  }
  private def compareAnnos[S <: T](reqAnnos: Set[String], optAnnos: Set[String], l: S, r: S): Boolean =
    (  (reqAnnos forall (a => (annotationsOf(l).get(a), annotationsOf(r).get(a)) match {
          case (Some(la), Some(ra)) => la == ra
          case _                    => false
        }))
    && (optAnnos forall (a => (annotationsOf(l).get(a), annotationsOf(r).get(a)) match {    	
    	  case (Some(la), Some(ra)) => la == ra
    	  case _                    => true          
    	}))
    )
  
  private def compareConsts[S <: T](reqOC: List[String], reqUC: Set[String], optOC: List[String], optUC: Set[String], l: S, r: S): Boolean =    
    (
       ((  (reqOC forall (label => (constituentsOf(l) exists (nameOf(_) == label)) && (constituentsOf(r) exists (nameOf(_) == label))))
        && (equivSeq(constituentsOf(l).toList filter (reqOC contains nameOf(_)), constituentsOf(r).toList filter (reqOC contains nameOf(_))))
       ))      
    &&
       ((  (reqUC forall (label => (constituentsOf(l) exists (nameOf(_) == label)) && (constituentsOf(r) exists (nameOf(_) == label))))
        && (equivSet(constituentsOf(l).toList filter (reqUC contains nameOf(_)), constituentsOf(r).toList filter (reqUC contains nameOf(_))))
       ))
    &&
       (((exoptOC: List[String]) =>
         equivSeq(constituentsOf(l).toList filter (exoptOC contains nameOf(_)), constituentsOf(r).toList filter (exoptOC contains nameOf(_)))
       )(optOC filter (label => (constituentsOf(l) exists (nameOf(_) == label)) && (constituentsOf(r) exists (nameOf(_) == label)))))
    &&
       (((exoptUC: Set[String]) =>
        equivSet(constituentsOf(l).toList filter (exoptUC contains nameOf(_)), constituentsOf(r).toList filter (exoptUC contains nameOf(_)))
       )(optUC filter (label => (constituentsOf(l) exists (nameOf(_) == label)) && (constituentsOf(r) exists (nameOf(_) == label)))))
    )
  
  private def findEquivTo[S <: T](elem: S, ctx: Seq[S], acc: Seq[S]): Slit[S] = ctx match {
    case Nil | Seq.empty =>
      Slit(None,None,acc)
      
    case _ if equiv(elem,ctx(0)) =>
      if(ordered(elem)) acc match {
        case Nil | Seq.empty => Slit(None, Some(ctx(0)), ctx.drop(1))
        case _               => Slit(Some(acc), Some(ctx(0)), ctx.drop(1))
      } else Slit(None, Some(ctx(0)),acc ++ ctx.drop(1))
      
    case _ =>
      findEquivTo(elem, ctx.drop(1), acc ++ Seq(ctx(0)))
  }  
}